package LeetCode;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;

public class LC_327_CountofRangeSum {

    public static void main(String[] args) {

    }

    static class Solution {
        public int countRangeSum(int[] nums, int lower, int upper) {
            if (nums == null || nums.length == 0) return 0;
            long[] sums = new long[nums.length];
            sums[0] = nums[0];
            for (int i = 1; i < nums.length; i++) sums[i] = sums[i - 1] + nums[i];
            int total = 0;
            TreeMap<Long, Integer> treemap = new TreeMap<>();
            for (int i = 0; i < nums.length; i++) {
                if (lower <= sums[i] && sums[i] <= upper) total++;
                for (Integer count : treemap.subMap(sums[i] - upper, true, sums[i] - lower, true).values())
                    total += count;
                Integer count = treemap.get(sums[i]);
                if (count == null) count = 1;
                else count++;
                treemap.put(sums[i], count);
            }
            return total;
        }

    }

    public class Solution_2 {
        private Node build(long[] nums, int from, int to) {
            if (from > to) return null;
            int m = (from + to) / 2;
            Node node = new Node(nums[m]);
            if (from < m) node.left = build(nums, from, m - 1);
            if (m < to) node.right = build(nums, m + 1, to);
            return node;
        }

        private void update(Node node, long val) {
            if (node == null) return;
            if (val < node.val) {
                node.count++;
                update(node.left, val);
            } else if (val > node.val) {
                update(node.right, val);
            } else {
                node.count++;
            }
        }

        private int smaller(Node node, long val) {
            if (node == null) return 0;
            if (node.val <= val) {
                return node.count + smaller(node.right, val);
            } else {
                return smaller(node.left, val);
            }
        }

        public int countRangeSum(int[] nums, int lower, int upper) {
            if (nums == null || nums.length == 0)
                return 0;
            long[] sums = new long[nums.length];
            sums[0] = nums[0];
            for (int i = 1; i < nums.length; i++)
                sums[i] = sums[i - 1] + nums[i];
            Set<Long> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++)
                set.add(sums[i]);
            long[] unique = new long[set.size()];
            int u = 0;
            for (long s : set)
                unique[u++] = s;
            Arrays.sort(unique);
            Node root = build(unique, 0, unique.length - 1);
            int count = 0;
            for (long sum : sums) {
                if (lower <= sum && sum <= upper) count++;
                count += smaller(root, sum - lower) - smaller(root, sum - upper - 1);
                update(root, sum);
            }
            return count;
        }
    }

    class Node {
        long val;
        int count;
        Node left, right;

        Node(long val) {
            this.val = val;
        }
    }


    public class Solution_3 {
        private Node build(long[] nums, int from, int to) {
            if (from > to) return null;
            int m = (from + to) / 2;
            Node node = new Node(nums[m]);
            if (from < m)
                node.left = build(nums, from, m - 1);
            if (m < to)
                node.right = build(nums, m + 1, to);
            return node;
        }

        private void update(Node node, long val) {
            if (node == null) return;
            if (val < node.val) {
                node.count++;
                update(node.left, val);
            } else if (val > node.val) {
                update(node.right, val);
            } else {
                node.count++;
            }
        }

        private int smaller(Node node, long val) {
            if (node == null) return 0;
            if (node.val <= val) {
                return node.count + smaller(node.right, val);
            } else {
                return smaller(node.left, val);
            }
        }

        public int countRangeSum(int[] nums, int lower, int upper) {
            if (nums == null || nums.length == 0) return 0;
            long[] sums = new long[nums.length];
            sums[0] = nums[0];
            for (int i = 1; i < nums.length; i++)
                sums[i] = sums[i - 1] + nums[i];
            Set<Long> set = new HashSet<>();
            for (int i = 0; i < nums.length; i++)
                set.add(sums[i]);
            long[] unique = new long[set.size()];
            int u = 0;
            for (long s : set) unique[u++] = s;
            Arrays.sort(unique);
            Node root = build(unique, 0, unique.length - 1);
            int count = 0;
            for (long sum : sums) {
                if (lower <= sum && sum <= upper)
                    count++;
                count += smaller(root, sum - lower) - smaller(root, sum - upper - 1);
                update(root, sum);
            }
            return count;
        }
    }




}